SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Automatic parallelization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Automatic parallelization</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>

<b>Automatic parallelization</b>, also <b>auto parallelization</b>, or <b>autoparallelization</b> refers to converting sequential <a href="Source_code" title="Source code">code</a> into <a href="Multi-threaded" class="mw-redirect" title="Multi-threaded">multi-threaded</a> and/or <a href="Automatic_vectorization" title="Automatic vectorization">vectorized</a> code in order to use multiple processors simultaneously in a shared-memory <a href="Multiprocessor" class="mw-redirect" title="Multiprocessor">multiprocessor</a> (<a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">SMP</a>) machine.<sup id="cite_ref-Yehezkael_2000_1-0" class="reference"><a href="#cite_note-Yehezkael_2000-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Fully automatic parallelization of sequential programs is a challenge because it requires complex <a href="Program_analysis_(computer_science)" class="mw-redirect" title="Program analysis (computer science)">program analysis</a> and the best approach may depend upon parameter values that are not known at compilation time.<sup id="cite_ref-Fox-Williams_Messina_1994_2-0" class="reference"><a href="#cite_note-Fox-Williams_Messina_1994-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The programming control structures on which autoparallelization places the most focus are <a href="Control_flow#Loops" title="Control flow">loops</a>, because, in general, most of the <a href="Run_time_(program_lifecycle_phase)" class="mw-redirect" title="Run time (program lifecycle phase)">execution time</a> of a program takes place inside some form of loop.

There are two main approaches to parallelization of loops: pipelined multi-threading and cyclic multi-threading.<sup id="cite_ref-Campanoni-Jones-Holloway-Wei-Brooks_2012_3-0" class="reference"><a href="#cite_note-Campanoni-Jones-Holloway-Wei-Brooks_2012-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> For example, consider a loop that on each iteration applies a hundred operations, and runs for a thousand iterations. This can be thought of as a grid of 100 columns by 1000 rows, a total of 100,000 operations. Cyclic multi-threading assigns each row to a different thread. Pipelined multi-threading assigns each column to a different thread.

</p>

<div class="mw-heading mw-heading2"><h2 id="Automatic_parallelization_technique">Automatic parallelization technique</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Parse">Parse</h3></div>

<p>This is the first stage where the scanner will read the input source files to identify all static and extern usages. Each line in the file will be checked against pre-defined patterns to segregate into <a href="Token_(parser)" class="mw-redirect" title="Token (parser)">tokens</a>. These tokens will be stored in a file which will be used later by the

grammar engine. The grammar engine will check patterns of tokens that match with pre-defined rules to identify variables, loops, control

statements, functions etc. in the code.

</p>

<div class="mw-heading mw-heading3"><h3 id="Analyze">Analyze</h3></div>

<p>The <a href="Analyzer" class="mw-redirect" title="Analyzer">analyzer</a> is used to identify sections of code that can be executed concurrently. The analyzer uses the static data information provided by the scanner-parser. The analyzer will first find all the totally independent functions and mark them as individual tasks. The analyzer then finds which tasks have dependencies.

</p>

<div class="mw-heading mw-heading3"><h3 id="Schedule">Schedule</h3></div>

<p>The <a href="Scheduling_(computing)" title="Scheduling (computing)">scheduler</a> will list all the tasks and their dependencies on each other in terms of execution and start times. The scheduler will produce the optimal schedule in terms of number of processors to be used or the total execution time for the application.

</p>

<div class="mw-heading mw-heading3"><h3 id="Code_generation">Code generation</h3></div>

<p>The <a href="Scheduling_(computing)" title="Scheduling (computing)">scheduler</a> will generate a list of all the tasks and the details of the cores on which they will execute along with the time that they will execute for. The code Generator will insert special constructs in the code that will be read during execution by the scheduler. These constructs will instruct the scheduler on which core a particular task will execute along with the start and end times.

</p>

<div class="mw-heading mw-heading2"><h2 id="Cyclic_multi-threading">Cyclic multi-threading</h2></div>

<p>A cyclic multi-threading parallelizing compiler tries to <a href="Loop_splitting" title="Loop splitting">split up a loop</a> so that each <a href="Iteration" title="Iteration">iteration</a> can be executed on a separate <a href="Microprocessor" title="Microprocessor">processor</a> concurrently.

</p>

<div class="mw-heading mw-heading3"><h3 id="Compiler_parallelization_analysis">Compiler parallelization analysis</h3></div>

<p>The <i>compiler</i> usually conducts two passes of analysis before actual parallelization in order to determine the following:

</p>

<ul><li>Is it safe to parallelize the loop? Answering this question needs accurate <a href="Dependence_analysis" title="Dependence analysis">dependence analysis</a> and <a href="Alias_analysis" title="Alias analysis">alias analysis</a></li>

<li>Is it worthwhile to parallelize it? This answer requires a reliable estimation (modeling) of the program workload and the capacity of the parallel system.</li></ul>

<p>The first pass of the compiler performs a <a href="Dependence_analysis" title="Dependence analysis">data dependence analysis</a> of the loop to determine whether each iteration of the loop can be executed independently of the others. Data dependence can sometimes be dealt with, but it may incur additional overhead in the form of <a href="Message_passing" title="Message passing">message passing</a>, synchronization of <a href="Shared_memory_(interprocess_communication)" class="mw-redirect" title="Shared memory (interprocess communication)">shared memory</a>, or some other method of processor communication.

</p><p>The second pass attempts to justify the parallelization effort by comparing the theoretical execution time of the code after parallelization to the code's sequential execution time. Somewhat counterintuitively, code does not always benefit from parallel execution. The extra overhead that can be associated with using multiple processors can eat into the potential speedup of parallelized code.

</p>

<div class="mw-heading mw-heading3"><h3 id="Example">Example</h3></div>

<p>A loop is called DOALL if all of its iterations, in any given invocation, can be executed concurrently.

</p><p>The <a href="Fortran" title="Fortran">Fortran</a> code below is DOALL, and can be auto-parallelized by a compiler because each iteration is independent of the others, and the final result of array <code>z</code> will be correct regardless of the execution order of the other iterations.

</p>

<span class="w"> </span><span class="k">enddo</span>

</pre></div>

<p>There are many <a href="Pleasingly_parallel" class="mw-redirect" title="Pleasingly parallel">pleasingly parallel</a> problems that have such DOALL loops. For example, when <a href="Parallel_rendering" title="Parallel rendering">rendering</a> a ray-traced movie, each frame of the movie can be independently rendered, and each pixel of a single frame may be independently rendered.

</p><p>On the other hand, the following code cannot be auto-parallelized, because the value of <code>z(i)</code> depends on the result of the previous iteration, <code>z(i - 1)</code>.

</p>

<span class="w"> </span><span class="k">enddo</span>

</pre></div>

<p>This does not mean that the code cannot be parallelized. Indeed, it is equivalent to the DOALL loop

</p>

<span class="w"> </span><span class="k">enddo</span>

</pre></div>

<p>However, current parallelizing compilers are not usually capable of bringing out these parallelisms automatically, and it is questionable whether this code would benefit from parallelization in the first place.

</p>

<div class="mw-heading mw-heading2"><h2 id="Pipelined_multi-threading">Pipelined multi-threading</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Software_pipelining" title="Software pipelining">software pipelining</a></div>

<p>A pipelined multi-threading parallelizing compiler tries to break up the sequence of operations inside a loop into a series of code blocks, such that each code block can be executed on separate <a href="Microprocessor" title="Microprocessor">processors</a> concurrently.

</p><p>There are many pleasingly parallel problems that have such relatively independent code blocks, in particular systems using <a href="Pipes_and_filters" class="mw-redirect" title="Pipes and filters">pipes and filters</a>.

</p><p>For example, when producing live broadcast television, the following tasks must be performed many times a second:

</p>

<ol><li>Read a frame of raw pixel data from the image sensor,</li>

<li>Do MPEG <a href="Motion_compensation" title="Motion compensation">motion compensation</a> on the raw data,</li>

<li>Entropy compress the motion vectors and other data,</li>

<li>Break up the compressed data into packets,</li>

<li>Add the appropriate error correction and do a FFT to convert the data packets into <a href="COFDM" class="mw-redirect" title="COFDM">COFDM</a> signals, and</li>

<li>Send the COFDM signals out the TV antenna.</li></ol>

<p>A pipelined multi-threading parallelizing compiler could assign each of these six operations to a different processor, perhaps arranged in a <a href="Systolic_array" title="Systolic array">systolic array</a>, inserting the appropriate code to forward the output of one processor to the next processor.

</p><p>Recent research focuses on using the power of GPU's<sup id="cite_ref-Anantpur-Govindarajan_2013_4-0" class="reference"><a href="#cite_note-Anantpur-Govindarajan_2013-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> and multicore systems<sup id="cite_ref-Zhuang-Eichenberger-Luo-OBrien_5-0" class="reference"><a href="#cite_note-Zhuang-Eichenberger-Luo-OBrien-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> to compute such independent code blocks( or simply independent iterations of a loop) at runtime.

The memory accessed (whether direct or indirect) can be simply marked for different iterations of a loop and can be compared for dependency detection. Using this information, the iterations are grouped into levels such that iterations belonging to the same level are independent of each other, and can be executed in parallel.

</p>

<div class="mw-heading mw-heading2"><h2 id="Difficulties">Difficulties</h2></div>

<p>Automatic parallelization by compilers or tools is very difficult due to the following reasons:<sup id="cite_ref-Blitzprog_6-0" class="reference"><a href="#cite_note-Blitzprog-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li>dependence analysis is hard for code that uses indirect addressing, pointers, recursion, or indirect function calls because it is difficult to detect such dependencies at compile time;</li>

<li>loops have an unknown number of iterations;</li>

<li>accesses to global resources are difficult to coordinate in terms of memory allocation, I/O, and shared variables;</li>

<li><i>irregular algorithms</i> that use input-dependent indirection interfere with compile-time analysis and optimization.<sup id="cite_ref-Rünger_2006_7-0" class="reference"><a href="#cite_note-Rünger_2006-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Workaround">Workaround</h2></div>

<p>Due to the inherent difficulties in full automatic parallelization, several easier approaches exist to get a parallel program in higher quality.

One of these is to allow programmers to add "hints" to their programs to guide compiler parallelization, such as <a href="High_Performance_Fortran" title="High Performance Fortran">HPF</a> for <a href="Distributed_memory" title="Distributed memory">distributed memory</a> systems and <a href="OpenMP" title="OpenMP">OpenMP</a> or <a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a> for <a href="Shared_memory_(interprocess_communication)" class="mw-redirect" title="Shared memory (interprocess communication)">shared memory</a> systems.

Another approach is to build an interactive system between programmers and parallelizing tools/compilers. Notable examples are <a href="Vector_Fabrics%2C_B.V." title="Vector Fabrics, B.V.">Vector Fabrics</a>' Pareon, <a href="SUIF" class="mw-redirect" title="SUIF">SUIF</a> Explorer (The Stanford University Intermediate Format compiler), the Polaris compiler, and ParaWise (formally CAPTools).

Finally, another approach is hardware-supported <a href="Speculative_multithreading" title="Speculative multithreading">speculative multithreading</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Parallelizing_compilers_and_tools">Parallelizing compilers and tools</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Automatic_parallelization_tool" title="Automatic parallelization tool">Automatic parallelization tool</a></div>

<p>Most research <a href="Compiler" title="Compiler">compilers</a> for automatic parallelization consider <a href="Fortran" title="Fortran">Fortran</a> programs, because Fortran makes stronger guarantees about <a href="Aliasing_(computing)" title="Aliasing (computing)">aliasing</a> than languages such as <a href="C_(programming_language)" title="C (programming language)">C</a>. Typical examples are:

</p>

<ul><li><a rel="nofollow" class="external text" href="http://www.ece.northwestern.edu/cpdc/Paradigm/Paradigm.html">Paradigm compiler</a></li>

<li><a rel="nofollow" class="external text" href="https://engineering.purdue.edu/Cetus/Documentation/manual/ch02s02.html">Polaris compiler</a></li>

<li><a rel="nofollow" class="external text" href="https://scholarship.rice.edu/handle/1911/16677">Rice Fortran D compiler</a></li>

<li><a href="SUIF" class="mw-redirect" title="SUIF">SUIF</a> compiler</li>

<li><a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1155/1999/304639">Vienna Fortran compiler</a></li></ul>

<p>Recently, Aubert, Rubiano, Rusch, and Seiller<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> used a dependency analysis technique <sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> to automatically parallelise loops in <a href="C_(programming_language)" title="C (programming language)">C</a> code.

</p>

<ul><li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Parallelization_contract" title="Parallelization contract">Parallelization contract</a></li>

<li><a href="Polytope_model" title="Polytope model">Polytope model</a> also known as Polyhedral model</li>

<li><a href="Scalable_parallelism" title="Scalable parallelism">Scalable parallelism</a></li>

<li><a href="BMDFM" class="mw-redirect" title="BMDFM">BMDFM</a></li>

<li><a href="Vectorization_(disambiguation)" class="mw-redirect mw-disambig" title="Vectorization (disambiguation)">Vectorization</a></li>

<li><a href="SequenceL" title="SequenceL">SequenceL</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFYehezkael2000" class="citation book cs1">Yehezkael, Rafael (2000). <a rel="nofollow" class="external text" href="http://u.cs.biu.ac.il/~wiseman/para2001.pdf">"Experiments in Separating Computational Algorithm from Program Distribution and Communication"</a> <span class="cs1-format">(PDF)</span>. <i>Applied Parallel Computing. New Paradigms for HPC in Industry and Academia</i>. <a href="Lecture_Notes_in_Computer_Science" title="Lecture Notes in Computer Science">Lecture Notes in Computer Science</a>. Vol. 1947. <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>. pp. <span class="nowrap">268–</span>278. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-70734-4_32">10.1007/3-540-70734-4_32</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-41729-3</bdi>.</cite></span>

</li>

<li id="cite_note-Fox-Williams_Messina_1994-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Fox-Williams_Messina_1994_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFFoxWilliamsMessina1994" class="citation book cs1">Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). <i>Parallel Computing Works!</i>. <a href="Morgan_Kaufmann" class="mw-redirect" title="Morgan Kaufmann">Morgan Kaufmann</a>. pp. 575, 593. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-253-3</bdi>.</cite></span>

</li>

<li id="cite_note-Campanoni-Jones-Holloway-Wei-Brooks_2012-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Campanoni-Jones-Holloway-Wei-Brooks_2012_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFCampanoniJonesHollowayWei2012" class="citation book cs1">Campanoni, Simone; Jones, Timothy; Holloway, Glenn; Wei, Gu-Yeon; Brooks, David (2012). <a rel="nofollow" class="external text" href="http://helix.eecs.harvard.edu/index.php/DAC2012"><i>The HELIX Project: Overview and Directions</i></a>.</cite></span>

</li>

<li id="cite_note-Anantpur-Govindarajan_2013-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Anantpur-Govindarajan_2013_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAnantpurGovindarajan" class="citation web cs1">Anantpur, J.; Govindarajan, R. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20151006123251/http://hpc.serc.iisc.ernet.in/~jayvant/papers/CGO-2013.pdf">"Runtime dependence computation and execution of loops on heterogeneous systems"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://hpc.serc.iisc.ernet.in/~jayvant/papers/CGO-2013.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 6 October 2015<span class="reference-accessdate">. Retrieved <span class="nowrap">5 October</span> 2015</span>.</cite></span>

</li>

<li id="cite_note-Zhuang-Eichenberger-Luo-OBrien-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Zhuang-Eichenberger-Luo-OBrien_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFZhuangEichenbergerLuoO'Brien" class="citation cs2">Zhuang, X.; Eichenberger, A. E.; Luo, Y.; O'Brien, Kathryn Kevin, <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/220884771"><i>Exploiting Parallelism with Dependence-Aware Scheduling</i></a></cite></span>

</li>

<li id="cite_note-Blitzprog-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Blitzprog_6-0">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20140714111836/http://blitzprog.org/posts/automatic-parallelism-and-data-dependency">"Automatic parallelism and data dependency"</a>. Archived from <a rel="nofollow" class="external text" href="http://blitzprog.org/posts/automatic-parallelism-and-data-dependency">the original</a> on 14 July 2014.</cite></span>

</li>

<li id="cite_note-Rünger_2006-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-Rünger_2006_7-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFRünger2006" class="citation journal cs1">Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". <i>Parallel Algorithms and Cluster Computing</i>. Lecture Notes in Computational Science and Engineering. <b>52</b>: <span class="nowrap">3–</span>23. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-33541-2_1">10.1007/3-540-33541-2_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-33539-9</bdi>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFAubertRubianoRuschSeiller2023" class="citation book cs1">Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2023). "Distributing and Parallelizing Non-canonical Loops". <i>Verification, Model Checking, and Abstract Interpretation</i>. Lecture Notes in Computer Science. Vol. 13881. pp. <span class="nowrap">91–</span>108. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-031-24950-1_1">10.1007/978-3-031-24950-1_1</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-031-24949-5</bdi>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFMoyenRubianoSeiller2017" class="citation book cs1">Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Loop Quasi-Invariant Chunk Detection". <i>Automated Technology for Verification and Analysis</i>. Lecture Notes in Computer Science. Vol. 10482. pp. <span class="nowrap">91–</span>108. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-68167-2_7">10.1007/978-3-319-68167-2_7</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-68166-5</bdi>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFPountain1989" class="citation magazine cs1">Pountain, Dick (December 1989). <a rel="nofollow" class="external text" href="https://archive.org/details/byte-magazine-1989-12/page/n382/mode/1up">"Configuring parallel programs, Part 1: The Occam Transpiler, now under development, will make writing software for parallel processing easier"</a>. <i><a href="BYTE_(magazine)" class="mw-redirect" title="BYTE (magazine)">BYTE</a></i>. Vol. 14, no. 13. <a href="McGraw-Hill%2C_Inc." class="mw-redirect" title="McGraw-Hill, Inc.">McGraw-Hill, Inc.</a> pp. <span class="nowrap">349–</span>352. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0360-5280">0360-5280</a>. ark:/13960/t34188734<span class="reference-accessdate">. Retrieved <span class="nowrap">6 January</span> 2022</span>.</cite> (NB. Uses the term <i>Occam transpiler</i> as a synonym for a <a href="Source-to-source_compiler" title="Source-to-source compiler">source-to-source compiler</a> working as a <a href="Pre-processor" class="mw-redirect" title="Pre-processor">pre-processor</a> that takes a normal <a href="Occam_(programming_language)" title="Occam (programming language)">occam</a> program as input and derives a new occam source code as output with link-to-channel assignments etc. added to it thereby <i><a href="Computer_configuration" title="Computer configuration">configuring</a></i> it for <a href="Parallel_processing_(computing)" class="mw-redirect" title="Parallel processing (computing)">parallel processing</a> to run as efficient as possible on a network of <a href="Transputer" title="Transputer">transputers</a>.)</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Compiler_optimizations253" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Compiler_optimizations253" style="font-size:114%;margin:0 4em"><a href="Optimizing_compiler" title="Optimizing compiler">Compiler optimizations</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic block</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Local_value_numbering" class="mw-redirect" title="Local value numbering">Local value numbering</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Loop_optimization" title="Loop optimization">Loop</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Automatic vectorization</a></li>

<li><a href="Induction_variable" title="Induction variable">Induction variable</a></li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Loop fusion</a></li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a></li>

<li><a href="Loop_inversion" title="Loop inversion">Loop inversion</a></li>

<li><a href="Loop_interchange" title="Loop interchange">Loop interchange</a></li>

<li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Loop_splitting" title="Loop splitting">Loop splitting</a></li>

<li><a href="Loop_unrolling" title="Loop unrolling">Loop unrolling</a></li>

<li><a href="Loop_unswitching" title="Loop unswitching">Loop unswitching</a></li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a></li>

<li><a href="Strength_reduction" title="Strength reduction">Strength reduction</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow<br>analysis</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Common_subexpression_elimination" title="Common subexpression elimination">Common subexpression elimination</a></li>

<li><a href="Constant_folding" title="Constant folding">Constant folding</a></li>

<li><a href="Dead_store" title="Dead store">Dead store</a> elimination</li>

<li><a href="Induction_variable_recognition_and_elimination" class="mw-redirect" title="Induction variable recognition and elimination">Induction variable recognition and elimination</a></li>

<li><a href="Live-variable_analysis" title="Live-variable analysis">Live-variable analysis</a></li>

<li><a href="Upwards_exposed_uses" title="Upwards exposed uses">Upwards exposed uses</a></li>

<li><a href="Use-define_chain" title="Use-define chain">Use-define chain</a></li>

<li><a href="Reaching_definition" title="Reaching definition">Reaching definitions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Static_single-assignment_form" title="Static single-assignment form">SSA</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Global_value_numbering" class="mw-redirect" title="Global value numbering">Global value numbering</a></li>

<li><a href="Sparse_conditional_constant_propagation" title="Sparse conditional constant propagation">Sparse conditional constant propagation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Code_generation_(compiler)" title="Code generation (compiler)">Code generation</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Instruction_scheduling" title="Instruction scheduling">Instruction scheduling</a></li>

<li><a href="Instruction_selection" title="Instruction selection">Instruction selection</a></li>

<li><a href="Register_allocation" title="Register allocation">Register allocation</a></li>

<li><a href="Rematerialization" title="Rematerialization">Rematerialization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Functional</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deforestation_(computer_science)" title="Deforestation (computer science)">Deforestation</a></li>

<li><a href="Tail_call" title="Tail call">Tail-call elimination</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Global</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interprocedural_optimization" title="Interprocedural optimization">Interprocedural optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a></li>

<li><a href="Compile-time_function_execution" title="Compile-time function execution">Compile-time function execution</a></li>

<li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Expression_templates" title="Expression templates">Expression templates</a></li>

<li><a href="Inline_expansion" title="Inline expansion">Inline expansion</a></li>

<li><a href="Jump_threading" title="Jump threading">Jump threading</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li>

<li><a href="Profile-guided_optimization" title="Profile-guided optimization">Profile-guided optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Static analysis</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alias_analysis" title="Alias analysis">Alias analysis</a></li>

<li><a href="Array-access_analysis" title="Array-access analysis">Array-access analysis</a></li>

<li><a href="Control-flow_analysis" title="Control-flow analysis">Control-flow analysis</a></li>

<li><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow analysis</a></li>

<li><a href="Dependence_analysis" title="Dependence analysis">Dependence analysis</a></li>

<li><a href="Escape_analysis" title="Escape analysis">Escape analysis</a></li>

<li><a href="Pointer_analysis" title="Pointer analysis">Pointer analysis</a></li>

<li><a href="Shape_analysis_(program_analysis)" title="Shape analysis (program analysis)">Shape analysis</a></li>

<li><a href="Value_range_analysis" title="Value range analysis">Value range analysis</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-24" href="https://en.wikipedia.org/wiki/?title=Automatic_parallelization&oldid=1297167952">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>